/**
 *
 * <p>Suffix Array.</p>
 *
 * <p>Suffix array is the array of all sorted suffixes of a string. To make suffix array useful in many string matching
 * problem, we usually compute auxiliary data structure such as LCP.</p>
 *
 *
 * <p>Longest common prefix (LCP) array is the array of lcp between pairs of consecutive suffixes in a suffix array.
 * For example, for the text {@code banana¥}, the corresponding suffix array is [6 5 3 1 0 4 2]. The lcp array will be
 * [0 0 1 3 0 0 2].</p>
 *
 * <pre>
 *  S: banana¥
 *
 *  i  SA LCP S
 *  0  6  0   ¥
 *  1  5  0   a¥
 *  2  3  1   ana¥
 *  3  1  3   anana¥
 *  4  0  0   banana¥
 *  5  4  0   na¥
 *  6  2  2   nana¥
 *
 * </pre>
 *
 * <p>Suffix array and suffix tree are very closely related. Suffix tree can be built from suffix tree in $O(n)$ and vice
 * versa. To build suffix array from suffix tree, use lexicographical order depth-first-search traversal.</p>
 *
 * <p>Suffix tree is one of the most important data structures that helps solve many problems in linear time. However,
 * suffix tree requires more space than suffix array and is a bit complicated to build.
 * Most of the problems solved by suffix tree can be solved by suffix array in linear time. Therefore,
 * quite a few papers is dedicated to suffix array.</p>
 *
 * <p>It's trivial to build SA in $O(n^2)$ by sorting suffixes in lexicographical order. This method can utilize any
 * methods of sorting strings such as MSD, LSD or radix quicksort etc. However, these methods do not utilize the fact that
 * these are suffixes.</p>
 *
 * <p>With SA and the LCP array, one can build suffix tree for S in linear time.</p>
 * <p>Building the suffix tree from the SA and LCP is just like the same way the DFS traversal does. We will build
 * the suffix tree in the order left to right of the SA. Start with root,
 * go down the left for the first suffix (ended at a leave), the walk up (how many steps depend on LCP), then walk
 * down to the next suffix. You keep going up and down. Going down is a constant. Going up is not necessary a constant
 * time, however, for the nodes you visit when you walk up, you never visit them again when walking up later. So the
 * algorithm runs in O(n) time.</p>
 *
 * @author Trung Phan
 *
 */
package net.tp.algo.text.sa;
